package two.chapter_1.c1_5;

public class WeightedQuickUnionUF extends UF {

    private int[] sz;
    public WeightedQuickUnionUF(int N) {
        super(N);
        sz=new int[N];
        for (int i=0;i<N;i++){
            sz[i]=1;
        }
    }

    @Override
    public void union(int p, int q) {
        int pId=find(p);
        int qId=find(q);
        if (pId!=qId){
            if (sz[pId]>sz[qId]){//将小树挂到大树上
                ids[qId]=pId;
                sz[pId]=sz[pId]+sz[qId];
            }else {
                ids[pId]=qId;
                sz[qId]=sz[pId]+sz[qId];
            }

            count--;
        }
    }

    /**
     * 对于N个触点，加权quick-union算法构造的森林中的任意节点的深度最多为lgN
     * @param p
     * @return
     */
    @Override
    public int find(int p) {
        while (ids[p]!=p){
            p=ids[p];
        }
        return p;
    }
}
